package com.lry.basic.algorithm.common;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/10/15
 */
public class FindDuplicate {
    public static void main(String[] args) {
        FindDuplicate fd = new FindDuplicate();
        System.out.println(fd.findDuplicate1(new int[]{1,3,2,2}));
    }
    public int findDuplicate1(int[] nums) {
        int tortoise = nums[0];
        int hare = nums[0];

        while (tortoise == hare){
            tortoise = nums[tortoise];
            hare = nums[nums[hare]];
        }

        int ptr1 = nums[0];
        int ptr2 = tortoise;
        while (ptr1 != ptr2) {
            ptr1 = nums[ptr1];
            ptr2 = nums[ptr2];
        }

        return ptr1;
    }

    public int findDuplicate(int[] nums) {
        int len = nums.length;
        int left = 1;
        int right = len-1;

        while(left<right){
            int mid = (left+right)>>>1;
            int count=0;
            for (int num:nums) {
                if(num<=mid){
                    count++;
                }
            }
            if(count>mid){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        return left;
    }
}
